/*
Date:20210411 10:14am
key:1.三个走向，所以三根指针，首先同一个起点，三个走向结果最小的那个返回来看看用的是哪个指针，哪一个就往前走一步。注意返回最小结果先对比A[n-1],如果是一样的就只让对应指针往前走，而不填入当前A[i]。
*/
class Solution {
public:
    int min(int a,int b,int c)
    {
        if(a<=b&&a<=c)
        {
            return a;
        }
        if(b<=a&&b<=c)
        {
            return b;
        }
        if(c<=b&&c<=a)
        {
            return c;
        }
        return 0;
    }
    int nthUglyNumber(int n) {
        if(n<=6)
        {
            return n;
        }
        int*A=new int[n];
        int t,y,u;
        t=0;
        y=0;
        u=0;
        int T,Y,U;
        for(int i=0;i<n;i++)
        {
            if(i==0)
            {
                A[i]=1;
            }
            else
            {
                T=A[t]*2;
                Y=A[y]*3;
                U=A[u]*5;
                A[i]=min(T,Y,U);
                if(A[i-1]==A[i])
                {
                    i--;
                }
                if(A[i]==T)
                {
                    t++;
                    continue;
                }
                if(A[i]==Y)
                {
                    y++;
                    
                }
                else{u++;}
            }
        }
        for(int i=0;i<n;i++)
        {
            cout<<A[i]<<" ";
        }
        return A[n-1];
    }
};